package com.gitee.feizns.explore.data_structure.graph.utils;

import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @author feizns
 * @since 2020/2/27
 */
public class Graph<K> implements Cloneable {

    private Map<K, Set<K>> graph;

    public Graph() {
        graph = new HashMap<>();
    }

    public void addEdge(K s, K t) {
        Set<K> ks = graph.get(s);
        if ( ks == null )
            ks = new HashSet<>();
        if ( s != t && !s.equals(t) )
            ks.add(t);
        graph.put(s, ks);
    }

    public Set<K> adj(K k) {
        Set<K> ks = graph.get(k);
        return ks != null ? ks : Collections.emptySet();
    }

    public Set<K> nodes() {
        return graph.keySet();
    }

    public int size() {
        return nodes().size();
    }

    @Override
    public Graph clone() {
        Graph graph = new Graph();
        for (K node : nodes()) {
            Set adj = adj(node);
            for (Object o : adj)
                graph.addEdge(node, o);
        }
        return graph;
    }

}
